package main

import "go-leetcode/leetcode/utils"

// 146. LRU 缓存
func main() {
}

type LRUCache struct {
	size       int
	capacity   int
	cacheMap   map[int]*utils.DLinkedNode
	head, tail *utils.DLinkedNode
}

func Constructor(capacity int) LRUCache {
	head := &utils.DLinkedNode{}
	tail := &utils.DLinkedNode{}
	head.Next = tail
	tail.Prev = head
	cacheMap := make(map[int]*utils.DLinkedNode)

	return LRUCache{
		size:     0,
		capacity: capacity,
		cacheMap: cacheMap,
		head:     head,
		tail:     tail,
	}
}

func (this *LRUCache) Get(key int) int {
	if node, exists := this.cacheMap[key]; exists {
		this.MoveToHead(node)
		return node.Value
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	if node, exists := this.cacheMap[key]; exists {
		node.Value = value
		this.MoveToHead(node)
	} else {
		newNode := &utils.DLinkedNode{
			Key:   key,
			Value: value,
		}
		this.AddToHead(newNode)
		this.cacheMap[newNode.Key] = newNode
		this.size++

		if this.size > this.capacity {
			deleteNode := this.tail.Prev
			this.DeleteNode(deleteNode)
			delete(this.cacheMap, deleteNode.Key)
			this.size--
		}
	}
}

func (this *LRUCache) MoveToHead(node *utils.DLinkedNode) {
	this.DeleteNode(node)
	this.AddToHead(node)
	return
}

func (this *LRUCache) AddToHead(newNode *utils.DLinkedNode) {
	oldNode := this.head.Next
	this.head.Next = newNode
	newNode.Prev = this.head
	newNode.Next = oldNode
	oldNode.Prev = newNode
	return
}

func (this *LRUCache) DeleteNode(node *utils.DLinkedNode) {
	node.Prev.Next = node.Next
	node.Next.Prev = node.Prev
	return
}

// 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
//实现 LRUCache 类：
//LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
//int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
//void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
//函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
//
//示例：
//
//输入
//["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
//[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
//输出
//[null, null, null, 1, null, -1, null, -1, 3, 4]
//
//解释
//LRUCache lRUCache = new LRUCache(2);
//lRUCache.put(1, 1); // 缓存是 {1=1}
//lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
//lRUCache.get(1);    // 返回 1
//lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
//lRUCache.get(2);    // 返回 -1 (未找到)
//lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
//lRUCache.get(1);    // 返回 -1 (未找到)
//lRUCache.get(3);    // 返回 3
//lRUCache.get(4);    // 返回 4
//
//提示：
//
//1 <= capacity <= 3000
//0 <= key <= 10000
//0 <= value <= 105
//最多调用 2 * 105 次 get 和 put
